package com.rgs.se.sort;

import java.util.Scanner;


public class P129_10 {

    /*交换数组中的两个数*/
    public static int[] Temp(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }

    /*快速排序*/
    public static void sort(int[] a, int low, int high) {
//这是递归的终止条件
        if(low>=high) {
            return;
        }
        //第一轮排序中，把low开始，hight作位结束,a[i]作位基准值
        int i = low;
        int j = high;
        int k = a[i];

//这是一轮排序结束的条件
        while(i<j) {
            //当a[j]>基准时，j就向左移。i<j是为了防止J越界。
            while (a[j] >= k&&i<j) {
                j--;
            }

//然后交换
            int t = 0;
            t = a[j];
            a[j] = a[i];
            a[i] = t;

//当a[i]<基准时，j就向右移。i<j是为了防止i越界。
            while (a[i] <= k&&i<j) {
                i++;
            }
            t = a[j];
            a[j] = a[i];
            a[i] = t;
        }

        //左边和右边递归排序
        sort(a,low,i-1);
        sort(a,i+1,high);
    }

    /*贪心算法解决独木舟载人问题*/
    public static int Byboat(int n,int w){
        int[] arr = new int[n];
        int left = 0;
        int right = n-1;
        int count = 0;
        Scanner in = new Scanner(System.in);
        //给每个人的体重赋值
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        /*
            调用快速排序对每个人的体重的大小进行排序
        */
        sort(arr,0,n-1);
        /*两侧指针网中间扫描*/
        while((right-left) > 1){
            if ((arr[right]+arr[left]) > w){
                count++;
                right--;
            } else{
                left++;
                right--;
                count++;
            }
        }
        if (left == right){
            count++;
        }
        if((right-left) == 1){
            if ((arr[right]+arr[left]) > w){
                count = count+2;
            }else {
                count++;
            }
        }
        System.out.println("最少需要的船数为：");
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入乘船人数n=");
        int n = in.nextInt();
        System.out.println("请输入船的最大载重w=");
        int w = in.nextInt();
        System.out.println("请依次输入每个人的体重：");
        System.out.println(Byboat(n,w));

    }
}
